package com.monkeyboy.tree;

import com.monkeyboy.TreeNode;

/**
 * 判断一个二叉树是不是另一个二叉树的子结构
 * 解题思路：
 * 从树的根节点进行判断，找出与另一个子节点的相等的序列
 *
 * @Author Gavin
 * @date 2021.04.18 14:11
 */
public class Tree03 {
    public boolean hasSub(TreeNode p1, TreeNode p2) {
        if (p2 == null) {
            return false;
        }
        if (p1 == null) {
            return false;
        }
        //is(p1,p2)的作用是从根节点开始判断，所以首先第一个先从根节点开始，如果不满足再从左右节点开始
        return isSub(p1, p2) || hasSub(p1.left, p2) || hasSub(p1.right, p2);
    }

    //递归判断两个序列是不是相同的序列
    public boolean isSub(TreeNode root1, TreeNode root2) {
        if (root2 == null) {
            return true;
        }
        if (root1 == null) {
            return false;
        }
        if (root1.val == root2.val) {
            return isSub(root1.left, root2.left) && isSub(root1.right, root2.right);
        }
       return false;
    }
}
